# LeetCode 105、从前序与中序遍历序列构造二叉树

# 一、题目描述

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

# 二、题目解析

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 从前序与中序遍历序列构造二叉树( LeetCode 105 ):https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        // 题目中说 preorder 和 inorder 均无重复元素
        // 通过哈希表把中序遍历序列中的值和顺序建立映射关系
        HashMap<Integer, Integer> map = new HashMap<>();

        // 通过 for 循环,遍历完中序遍历序列中的所有元素
        for (int i = 0; i < inorder.length; i++) {
             // 以中序序列中的元素值 inorder[i] 作为 key
             // 以位置 i 作为 value
             // 存放到哈希表中
             // 比如中序遍历序列中的元素是 [   A  ,   D  ,   E  ,   F  ,   G  ,   H  ,   M  ,   Z  ]
             // 那么这个哈希表就是以下的样子
             // | 索引 | 位置  |
             // | A | 0  |
             // | D | 1  |
             // | E | 2  | 
             // | F | 3  | 
             // | G | 4  | 
             // | H | 5  | 
             // | M | 6  | 
             // | Z | 7  |            
             map.put(inorder[i], i);
        }

        // 下面开始构建二叉树
        // 把前序遍历序列中的第一个元素 preorder[0] 作为二叉树的根节点
        // 因为任意二叉树的前序遍历序列中的第一个元素,一定是二叉树的根节点
        TreeNode root = new TreeNode(preorder[0]);


        // 继续遍历前序遍历序列中的其它元素
        for(int i = 1 ; i < preorder.length ; i++){

            // 把当前遍历的元素构造为一个二叉树的节点
            TreeNode node = new TreeNode(preorder[i]);

            // 把构造的节点插入到以 root 为根节点的二叉树中
            insertNode(root,node,map);

        }

        // 当 preorder 中所有元素都构造并且插入完毕之后
        // 二叉树就完成了构建
        return root;


    }

    // root : 二叉树的根节点
    // node : 待插入的节点
    // map : 节点值和中序遍历序列位置的映射
    private void insertNode(TreeNode root,TreeNode node,HashMap<Integer,Integer> map){

            // 当 root 和 node 指向的节点相同时,跳出循环
            while(root != node){

                // 如果 node 的中序遍历序列位置小于 root 的中序遍历序列位置
                // 说明 node 应该在 root 的左子树中
                if(map.get(node.val) < map.get(root.val)){

                    // 如果此时 root 没有左子树
                    if(root.left == null){
                        // 那么就把 node 设置为 root 的左子树
                        root.left = node;
                    }

                    // 1、如果之前 root 没有左子树,那么通过上面的代码,就设置好了 root 的左子树
                    // 也就是说 node 是 root 的一个叶子节点,完成了插入操作
                    // 把 root 指向 root.left 后,root 为 node,跳出了循环

                    // 2、如果之前 root 已经有左子树,那么就不能直接把 node 插入到 root 的左子树上
                    // 需要判断应该把 node 插入到 root 左子树上的孩子节点的那个位置上
                    // 比如现在的 root 是这个样子,node 为 A
                    //        G
                    //       /
                    //      D
                    //     /  \
                    //    ①   ②
                    // root 已经有左子树 D 了,所以 node 应该考虑插入到 D 中的 ① 还是 ② 上面
                    // 所以,把 root 指向 root.left ,继续遍历 root 的左子树的情况
                    root = root.left;

                    
                }else{

                    // 如果 node 的中序遍历序列位置大于 root 的中序遍历序列位置
                    // 说明 node 应该在 root 的右子树中
                    
                    // 如果此时 root 没有右子树
                    if(root.right == null){
                        // 那么就把 node 设置为 root 的右子树
                        root.right = node;
                    }

                    // 把 root 指向 root.right ,继续遍历 root 的右子树的情况
                    root = root.right;
                    
                }

            }
    }
}

# **2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 从前序与中序遍历序列构造二叉树( LeetCode 105 ):https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
class Solution {

    // 题目中说 preorder 和 inorder 均无重复元素
    // 通过哈希表把中序遍历序列中的值和顺序建立映射关系
    unordered_map<int, int> map;

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {

        // 通过 for 循环,遍历完中序遍历序列中的所有元素
        for (int i = 0; i < inorder.size(); i++) {
             // 以中序序列中的元素值 inorder[i] 作为 key
             // 以位置 i 作为 value
             // 存放到哈希表中
             // 比如中序遍历序列中的元素是 [   A  ,   D  ,   E  ,   F  ,   G  ,   H  ,   M  ,   Z  ]
             // 那么这个哈希表就是以下的样子
             // | 索引 | 位置  |
             // | A | 0  |
             // | D | 1  |
             // | E | 2  | 
             // | F | 3  | 
             // | G | 4  | 
             // | H | 5  | 
             // | M | 6  | 
             // | Z | 7  |            
             map[inorder[i]] =  i;
        }

        // 下面开始构建二叉树
        // 把前序遍历序列中的第一个元素 preorder[0] 作为二叉树的根节点
        // 因为任意二叉树的前序遍历序列中的第一个元素,一定是二叉树的根节点
        TreeNode *root = new TreeNode(preorder[0]);

        // 继续遍历前序遍历序列中的其它元素
        for(int i = 1 ; i < preorder.size() ; i++){

            // 把当前遍历的元素构造为一个二叉树的节点
            TreeNode *node = new TreeNode(preorder[i]);

            // 把构造的节点插入到以 root 为根节点的二叉树中
            insertNode(root,node);

        }

        // 当 preorder 中所有元素都构造并且插入完毕之后
        // 二叉树就完成了构建
        return root;
    }

    // root : 二叉树的根节点
    // node : 待插入的节点
private:
       void insertNode(TreeNode *root,TreeNode *node){

            // 当 root 和 node 指向的节点相同时,跳出循环
            while(root != node){

                // 如果 node 的中序遍历序列位置小于 root 的中序遍历序列位置
                // 说明 node 应该在 root 的左子树中
                if(map[node->val] < map[root->val]){

                    // 如果此时 root 没有左子树
                    if(root->left == NULL){
                        // 那么就把 node 设置为 root 的左子树
                        root->left = node;
                    }

                    // 1、如果之前 root 没有左子树,那么通过上面的代码,就设置好了 root 的左子树
                    // 也就是说 node 是 root 的一个叶子节点,完成了插入操作
                    // 把 root 指向 root.left 后,root 为 node,跳出了循环

                    // 2、如果之前 root 已经有左子树,那么就不能直接把 node 插入到 root 的左子树上
                    // 需要判断应该把 node 插入到 root 左子树上的孩子节点的那个位置上
                    // 比如现在的 root 是这个样子,node 为 A
                    //        G
                    //       /
                    //      D
                    //     /  \
                    //    ①   ②
                    // root 已经有左子树 D 了,所以 node 应该考虑插入到 D 中的 ① 还是 ② 上面
                    // 所以,把 root 指向 root.left ,继续遍历 root 的左子树的情况
                    root = root->left;


                }else{

                    // 如果 node 的中序遍历序列位置大于 root 的中序遍历序列位置
                    // 说明 node 应该在 root 的右子树中

                    // 如果此时 root 没有右子树
                    if(root->right == NULL){
                        // 那么就把 node 设置为 root 的右子树
                        root->right = node;
                    }

                    // 把 root 指向 root.right ,继续遍历 root 的右子树的情况
                    root = root->right;

                }

            }
    }
};

# 3、Python 代码

#登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 从前序与中序遍历序列构造二叉树( LeetCode 105 ):https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
class Solution:

    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:

        # 题目中说 preorder 和 inorder 均无重复元素
        # 通过哈希表把中序遍历序列中的值和顺序建立映射关系
        # 通过 for 循环,遍历完中序遍历序列中的所有元素
        map = dict()

        for i in range(len(inorder)) :
             # 以中序序列中的元素值 inorder[i] 作为 key
             # 以位置 i 作为 value
             # 存放到哈希表中
             # 比如中序遍历序列中的元素是 [   A  ,   D  ,   E  ,   F  ,   G  ,   H  ,   M  ,   Z  ]
             # 那么这个哈希表就是以下的样子
             # | 索引 | 位置  |
             # | A | 0  |
             # | D | 1  |
             # | E | 2  | 
             # | F | 3  | 
             # | G | 4  | 
             # | H | 5  | 
             # | M | 6  | 
             # | Z | 7  |  
            map[inorder[i]] =  i


        # 下面开始构建二叉树
        # 把前序遍历序列中的第一个元素 preorder[0] 作为二叉树的根节点
        # 因为任意二叉树的前序遍历序列中的第一个元素,一定是二叉树的根节点
        root =  TreeNode(preorder[0])


        # 继续遍历前序遍历序列中的其它元素
        for i in range( 1 ,len(preorder)):

            # 把当前遍历的元素构造为一个二叉树的节点
            node = TreeNode(preorder[i])

            # 把构造的节点插入到以 root 为根节点的二叉树中
            self.insertNode(root,node,map)



        # 当 preorder 中所有元素都构造并且插入完毕之后
        # 二叉树就完成了构建
        return root

    # root : 二叉树的根节点
    # node : 待插入的节点
    def insertNode(self , root : TreeNode, node : TreeNode,map:dict) :
            # 当 root 和 node 指向的节点相同时,跳出循环
            while root != node : 

                # 如果 node 的中序遍历序列位置小于 root 的中序遍历序列位置
                # 说明 node 应该在 root 的左子树中
                if map[node.val] < map[root.val] : 

                    # 如果此时 root 没有左子树
                    if not root.left : 
                        # 那么就把 node 设置为 root 的左子树
                        root.left = node
                    

                    # 1、如果之前 root 没有左子树,那么通过上面的代码,就设置好了 root 的左子树
                    # 也就是说 node 是 root 的一个叶子节点,完成了插入操作
                    # 把 root 指向 root.left 后,root 为 node,跳出了循环

                    # 2、如果之前 root 已经有左子树,那么就不能直接把 node 插入到 root 的左子树上
                    # 需要判断应该把 node 插入到 root 左子树上的孩子节点的那个位置上
                    # 比如现在的 root 是这个样子,node 为 A
                    #        G
                    #       /
                    #      D
                    #     /  \
                    #    ①   ②
                    # root 已经有左子树 D 了,所以 node 应该考虑插入到 D 中的 ① 还是 ② 上面
                    # 所以,把 root 指向 root.left ,继续遍历 root 的左子树的情况
                    root = root.left

                    
                else:

                    # 如果 node 的中序遍历序列位置大于 root 的中序遍历序列位置
                    # 说明 node 应该在 root 的右子树中
                    
                    # 如果此时 root 没有右子树
                    if not root.right : 
                        # 那么就把 node 设置为 root 的右子树
                        root.right = node
                    

                    # 把 root 指向 root.right ,继续遍历 root 的右子树的情况
                    root = root.right